package com.jacklei.tree;
//满二叉树
public class FullBinaryTree {

    private static int num;

    static class Node{
        int value;
        Node right;
        Node left;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);

        root.left = new Node(2);
        root.right = new Node(3);

        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println(checkFullBinaryTree(root));

    }
    public static boolean checkFullBinaryTree(Node root) {
        num = 0;
        return  ((1 << FullNum(root)) - 1) == num;
    }

    //求出树的最高高度
     //节点个数
    public static int FullNum(Node root) {
        if(root == null) return 0;

        int left = FullNum(root.left) + 1;

        int right = FullNum(root.right) + 1;
        num++;
        return  Math.max(left, right);
    }

}
